package algorithm.sort;

import java.io.IOException;

/**
 * 冒泡排序
 * 时间复杂度    O(n^2)
 * 冒泡排序是是稳定的排序算法
 * 
 * 优化思路：如果某次比较过程中，发现没有任何元素移动，则不再进行接下来的比较；
 * 					 记下最后一次交换的位置，后边没有交换，必然是有序的，然后下一次排序从第一个比较到上次记录的位置结束即可；
 * 					 进行双向循环，正向循环把最大元素移动到数组末尾，逆向循环把最小元素移动到数组首部。该种排序方式也叫双向冒泡排序
 * 
 * 适用场景：适用于数据量很小的排序场景
 * */
public class BubbleSort {
    public static void sort(int[] arr) {
        for(int i = 1; i < arr.length; i++) {
            for(int j = 0; j < arr.length - i; j++) {
                if(arr[j] > arr[j + 1]) 
                	Swap.swap(arr, j, j + 1);
            }
        }
    }
    
    public static void sortOptimize(int[] arr) {    // 优化
        for(int i = arr.length - 1, end = i; i > 0; i--) {
            boolean isSwap = false;
            int last = 0;
            for(int j = 0; j < end; j++) {
                if(arr[j] > arr[j + 1]) {
                	Swap.swap(arr, j, j + 1);
                    isSwap = true;
                    last = j;   // 记下最后一次交换的位置，后边没有交换，必然是有序的
                                // 然后下一次排序从第一个比较到上次记录的位置结束即可
                }
            }
            if(!isSwap)     // 本轮比较中没有发生交换则退出外循环，即已排序好
                break;
            end = last;     // 下一轮比较所需要比较到的位置
        }
    }
    
    public static void sortOptimize2(int[] arr) {		// 优化，双向遍历
    	for(int left = 0, right = arr.length - 1; left < right;) {
            int last_left = left, last_right = right;
            boolean isSwap = false;
            for(int i = left; i < right; i++)
                if (arr[i] > arr[i + 1]) {
                    Swap.swap(arr, i, i + 1);
                    isSwap = true;
                    last_right = i;   // 记录正向最后一次交换的位置，后边没有交换，必然是有序的
                }
            if(!isSwap)		// 本轮比较中没有发生交换则退出外循环，即已排序好
            	break;
            for(int i = last_right; i > left; i--) {
                if(arr[i] < arr[i - 1]) {
                	Swap.swap(arr, i - 1, i);
                	last_left = i;		// 记录反向最后一次交换的位置，前边没有交换，必然是有序的
                }
            }
            left =  left != last_left ? last_left : left + 1;     				// 下一轮比较所需要比较的开始位置
            right = right != last_right ? last_right : right - 1;		// 下一轮比较所需要比较的结束位置
        }
    }

    public static void main(String[] args) throws IOException {
        int[] arr = InputSequence.inputIntArray();
//        BubbleSort.sort(arr);
        BubbleSort.sortOptimize2(arr);
        for(int i = 0; i < arr.length; i++)
            System.out.print(arr[i] + " ");
    }
}
